import java.util.Arrays;

public class Solution221 {
    // 修复前缀和计算的索引错误
    public int calcArea(int[][] prefixSum, int startX, int startY, int endX, int endY) {
        return prefixSum[endX][endY]
                - (startX == 0 ? 0 : prefixSum[startX - 1][endY])  // 减去上方矩形
                - (startY == 0 ? 0 : prefixSum[endX][startY - 1])  // 减去左方矩形（修正索引）
                + (startX == 0 || startY == 0 ? 0 : prefixSum[startX - 1][startY - 1]);  // 加回重叠部分
    }

    public int maximalSquare(char[][] matrix) {
        // 边界处理：空矩阵直接返回0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] prefixSum = new int[rows][cols];

        // 构建前缀和数组
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                prefixSum[i][j] = (matrix[i][j] - '0')  // 当前单元格值
                        + (i > 0 ? prefixSum[i - 1][j] : 0)  // 上方前缀和
                        + (j > 0 ? prefixSum[i][j - 1] : 0)  // 左方前缀和
                        - (i > 0 && j > 0 ? prefixSum[i - 1][j - 1] : 0);  // 减去重叠部分
            }
        }

        int maxArea = 0;
        // 尝试所有可能的正方形边长（从大到小可优化效率）
        for (int len = Math.min(rows, cols); len >= 1; len--) {
            // 遍历所有可能的正方形左上角
            for (int i = 0; i <= rows - len; i++) {
                for (int j = 0; j <= cols - len; j++) {
                    int endX = i + len - 1;  // 右下角X坐标
                    int endY = j + len - 1;  // 右下角Y坐标
                    // 若正方形区域内所有元素都是1（面积=边长²）
                    if (calcArea(prefixSum, i, j, endX, endY) == len * len) {
                        return len * len;  // 找到最大面积，直接返回
                    }
                }
            }
        }
        return maxArea;
    }

    /**
     * 我们用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。
     * 如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。
     *
     * @param matrix
     * @return
     */
    public int maximalSquare2(char[][] matrix) {
        // 边界处理：空矩阵直接返回0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxArea = 0;

        // 构建前缀和数组
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        //通俗易懂得理解方法是，因为本题需要得是正方形，因此仅需要保证周围点为1且加上自己构成正方形即可。如果左、上、左上有一个点为0，那么将无法转移。
                        int min = Integer.MAX_VALUE;
                        min = Math.min(min, dp[i - 1][j]);
                        min = Math.min(min, dp[i][j - 1]);
                        min = Math.min(min, dp[i - 1][j - 1]);
                        dp[i][j] = min + 1;

                    }
                }
                maxArea = Math.max(maxArea, dp[i][j] * dp[i][j]);
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution221 solution = new Solution221();
        char[][] matrix1 = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        System.out.println(solution.maximalSquare2(matrix1));  // 输出：4（2x2的正方形）

        char[][] matrix2 = {{'0', '0', '0'}, {'0', '0', '0'}, {'0', '0', '0'}, {'0', '0', '0'}};
        System.out.println(solution.maximalSquare2(matrix2));  // 输出：0（无1的正方形）
    }
}
